package bTree.LeetCode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class 重排链表 {
    public void reorderList(ListNode head) {
        int cnt=0;
        ListNode pp=head;
        while (pp!=null){
            cnt++;
            pp=pp.next;
        }
        Queue<ListNode>queue=new LinkedList<ListNode>();
        Stack<ListNode>stack=new Stack<ListNode>();
        ListNode p=head;
        int cnt2=1;
        while (p!=null) {
            if(cnt2<=cnt/2+cnt%2){
                queue.offer(p);
            }else {
                stack.push(p);
            }
            cnt2++;
            p = p.next;
        }
        ListNode preNode=head;
        queue.poll();
        cnt=0;
        while (!queue.isEmpty()||!stack.isEmpty()){
            if (cnt%2==0){
                   preNode.next=stack.peek();
                   preNode=stack.pop();
            }
            if (cnt%2==1){
                preNode.next=queue.peek();
                preNode=queue.poll();
            }
            cnt++;
        }
        preNode.next=null;
    }
}